{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rawdata = {\n",
    "    'no surfacing':[1,1,1,0,0],\n",
    "    'flippers':[1,1,0,1,1],\n",
    "    'fish':[ 'yes','yes','no','no','no']\n",
    "}\n",
    "\n",
    "df = pd.DataFrame(rawdata)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.shape[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.iloc[:,-1].value_counts() / df.shape[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p_v = df.iloc[:,-1].value_counts() / df.shape[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "-np.log2(p_v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p_v * -np.log2(p_v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.sum(p_v * -np.log2(p_v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calEnt(df):\n",
    "    m = df.shape[0]\n",
    "    p_v =df.iloc[:,-1].value_counts() / m\n",
    "    return np.sum(p_v * -np.log2(p_v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "calEnt(df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bestSplit(df):\n",
    "    baseEnt = calEnt(df)\n",
    "    bestCol = ''\n",
    "    bestGain = 0\n",
    "    infoGain = 0\n",
    "    for col in df.columns[:-1]:\n",
    "        p_v = df[col].value_counts(True)\n",
    "        ent_v = []\n",
    "\n",
    "        for col_value in p_v.index:\n",
    "            ent_v.append(calEnt(df[df[col]== col_value]))\n",
    "            colEnt = (p_v * ent_v).sum()\n",
    "            infoGain = baseEnt - colEnt\n",
    "            print(col,\"的 信息增益为:\",infoGain)\n",
    "            if (infoGain > bestGain):\n",
    "                bestGain = infoGain\n",
    "                bestCol = col\n",
    "\n",
    "    return bestCol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df['no surfacing'].value_counts(True).index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bestSplit(df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bestSplit(df.iloc[:,1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mySplit(df,bestCol,value):\n",
    "    return df[df[bestCol] == value].drop(bestCol,axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.iloc[:,-1].value_counts(True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.iloc[:,-1].value_counts(True).index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def createTree(df):\n",
    "\n",
    "    labelFreq = df.iloc[:,-1].value_counts(True)\n",
    "    if df.shape[1] == 1 or labelFreq[0] == 1:\n",
    "        return labelFreq.index[0]\n",
    "    bestCol = bestSplit(df)\n",
    "    tree = {bestCol:{}}\n",
    "    value_set = set(df[bestCol])\n",
    "\n",
    "    for value in value_set:\n",
    "        tree[bestCol][value] = createTree(mySplit(df,bestCol,value))\n",
    "    return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "myTree = createTree(df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.save('myTree.npy',myTree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.load('myTree.npy',allow_pickle=True).item()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "myTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(df.columns[:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(zip([0,1],list(df.columns)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inX = dict(zip(list(df.columns[:-1]),[0,1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[\"no syrfacing\",\"flippers\"]\n",
    "[0,1]\n",
    "\n",
    "{\n",
    "    \"no surfacing\":0,\n",
    "    \"filppers\":1\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getInXTree(inX,tree):\n",
    "    colName = next(iter(tree))\n",
    "    colValue = inX[colName]\n",
    "    return tree[colName][colValue]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def classify(inX,myTree):\n",
    "    inX = dict(zip(list(df.columns[:-1]),inX))\n",
    "    label = getInXTree(inX,myTree)\n",
    "    while (type(label) == dict):\n",
    "        label = getInXTree(inX,label)\n",
    "    return label"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "classify([1,1],myTree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_iris\n",
    "from sklearn import tree\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clf = tree.DecisionTreeClassifier(criterion=\"entropy\")\n",
    "clf = clf.fit(np.array(df.iloc[:, :-1]), np.array(df.iloc[:, -1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree.plot_tree(clf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df_l = pd.read_table('lenses.txt',header=None)\n",
    "df_l.columns=['age','prescript','astigmatil','tearRate','label']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(set(df_l.age))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(range(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dMap(df):\n",
    "    for col in df.columns[:-1]:\n",
    "        valueSet = set(df[col])\n",
    "        mapvaluelist = list(range(len(valueSet)))\n",
    "        d = dict(zip(list(valueSet),mapvaluelist))\n",
    "        df[col] = df[col].map(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dMap(df_l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.array(df_l.iloc[:,:-1])\n",
    "labels = np.array(df_l.iloc[:,-1])\n",
    "feature_names = np.array(df_l.columns[:-1])\n",
    "clf = tree.DecisionTreeClassifier(criterion=\"entropy\")\n",
    "clf = clf.fit(data,labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(200,90))\n",
    "\n",
    "tree.plot_tree(clf,feature_names=feature_names,class_names=labels,filled=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "a6dc62afd8b03c17538a9dfce2fcb18f62cec380cc7b77050462a64b7e4e4814"
  },
  "kernelspec": {
   "display_name": "Python 3.8.0 32-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.0"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
